package top.minuy.structure.graph.path.weighted;

import top.minuy.structure.graph.representations.table.WeightedGraph;
import top.minuy.structure.queue.PriorityQueueMin;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 带权图最短路径算法
 * 使用优先队列优化算法
 * 求出路径
 *
 * @author Minuy
 * @time 13:46
 * @date 2021/11/26
 */
public class DijkstraPQPath {
    private WeightedGraph g;
    private int[] dis;
    private boolean[] isVisited;
    private int[] pre;
    private int s;

    // 存储距离和顶点的类，配合优先队列使用
    private class Node implements Comparable<Node>{
        int dis;
        int v;
        private Node(int v,int dis){
            this.dis = dis;
            this.v = v;
        }


        @Override
        public int compareTo(Node node) {
            return this.dis-node.dis;
        }
    }

    public DijkstraPQPath(WeightedGraph g, int s) {
        this.g = g;

        g.validateVertex(s);
        this.s = s;

        pre = new int[g.V()];
        dis = new int[g.V()];
        for (int i = 0; i < dis.length; i++) {
            dis[i] = Integer.MAX_VALUE;
        }

        isVisited = new boolean[g.V()];

        dis[s] = 0;

        PriorityQueueMin<Node> pq = new PriorityQueueMin<>();
        pq.enqueue(new Node(s,0));

        while (!pq.isEmpty()) {
            // 找到图中路径最短的那个顶点
//            int minV = -1, minDis = Integer.MAX_VALUE;
//            for (int v = 0; v < g.V(); v++) {
//                if (!isVisited[v] && dis[v] < minDis) {
//                    minDis = dis[v];
//                    minV = v;
//                }
//            }

            // 找到路径最短的点
            int minV = pq.dequeue().v;

            // 如果是被确定了的点，就可以跳过
            if (isVisited[minV]) {
                continue;
            }

            isVisited[minV] = true;
            for (int v : g.adj(minV)) {
                if(!isVisited[v]) {
                    int newDis = dis[minV] + g.getWeight(v, minV);
                    if (newDis < dis[v]) {
                        dis[v] = newDis;
                        // 添加进优先队列
                        pq.enqueue(new Node(v,newDis));
                        // 更新路径父顶点
                        pre[v] = minV;
                    }
                }
            }

        }

    }

    public boolean isConnectedTo(int t){
        g.validateVertex(t);
        return isVisited[t];
    }

    public int disTo(int t){
        g.validateVertex(t);
        return dis[t];
    }

    public Iterable<Integer> path(int t){
        ArrayList<Integer> ret = new ArrayList<>();
        if (!isConnectedTo(t)){
            return ret;
        }

        int cur = t;
        while (cur!=s){
            ret.add(cur);
            cur = pre[cur];
        }
        ret.add(s);

        Collections.reverse(ret);
        return ret;
    }
}
